Алгоритмы быстрого возведения в степень
АЛГОРИТМ, ПРЕДНАЗНАЧЕННЫЙ ДЛЯ ВОЗВЕДЕНИЯ ЧИСЛА X В НАТУРАЛЬНУЮ СТЕПЕНЬ N ЗА МЕНЬШЕЕ ЧИСЛО УМНОЖЕНИЙ, ЧЕМ ЭТО ТРЕБУЕТСЯ В ОПРЕДЕЛЕНИИ СТЕПЕН
Быстрое возведение в степень; Алгоритм быстрого возведения в степень; Дихотомический алгоритм возведения в степень; Бинарный алгоритм возведения в степень; Возведение в степень «слева направо»
Алгоритмы быстрого возведения в степень (дихотомический алгоритм возведения в степень, бинарный алгоритм возведения в степень) — алгоритмы, предназначенные для возведения числа x в натуральную степень n за меньшее число умножений, чем это требуется в определении степени. Алгоритмы основаны на том, что для возведения числа x в степень n не обязательно перемножать число x на само себя n раз, а можно перемножать уже вычисленные степени. В частности, если n=2^k степень двойки, то для возведения в степень n достаточно число возвести в квадрат k раз, затратив пр�